package q1235_jobScheduling;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution_1 {
    /*
    规划兼职工作
    1.通过离散化对开始时间进行排序
    2.用小顶堆保存每个可得报酬的结束时间
    3.通过比较小于等于当前时间的每个结束时间的最大收益，获得当前最大报酬
     */
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        // 按照结束时间排序的小顶堆
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        // 离散化
        Integer[] idx = new Integer[n];
        for(int i = 0; i < n; i++){
            idx[i] = i;
        }
        // 对开始时间进行排序
        Arrays.sort(idx, Comparator.comparingInt(a -> startTime[a]));
        int max = 0;
        for(int i = 0; i < n; i++){
            int start = startTime[idx[i]];
            // 取出结束时间小于等于当前start的工作，得到当前可以得到的最大收益
            while(!pq.isEmpty() && pq.peek()[1] <= start){
                max = Math.max(max, pq.poll()[0]);
            }
            // 当前最大收益 + 结束时可得收益
            pq.offer(new int[]{max + profit[idx[i]], endTime[idx[i]]});
        }
        while(!pq.isEmpty()){
            max = Math.max(max, pq.poll()[0]);
        }
        return max;
    }
}
